'''
表达式tip:
对表达式进行语义分析时 尽可能保证 最终的运算结果保存到最初创建的临时寄存器中!!!
例如:最先分配t0 那么最后结果尽量都存到t0去 而非存到t10 t9这类,
这样可以缩减编号范围 便于后续优化缩减寄存器 
在调用表达式的一侧 应尽量重置当前最新的tn编号为 返回结果所在的寄存器,便于将高编号寄存器回收。
'''
'''
[数据结构新增]
为了适应语义分析并兼容留存之前的语法分析 我们对数据结构增改如下:
0.我们假定当前语义分析并不使用真正的寄存器，我们使用t0 t1 t2....tn 这样的临时结果"寄存器"
  为了处理的简便 retDict中新增一个当前最新临时寄存器编号变量 tn, 每一步骤出现变量时 需要为变量新建一个临时的tn来保存值 
1.retDict中新增 我们定义的名为asmCodes的列表结构 来保存每一步骤生成的中间四元式:
[
  {"row":行数(作为语句的偏移地址 用来指示跳转语句的目的地),"op":操作指令,"arg1":源参数,"arg2":目的参数,"res":产生新值应存到哪个结果当中},
  ....
  {同上构造的字典}
]
2.retDict中新增 我们定义一个返回本步骤值的结果: res



【retDict】是通用的结果字典 最顶层函数返回形式如下:
#  {
#     "status":结果状态(0异常|1正常),
#     "need":返回符合语法规则的token序列(token序列|None),
#     "new":剩下的token序列 (token序列|None),
#     "needTree":本次查找后得到的语法树字典(语法树字典|None),
#     "asmCodes":从下层返回的四元式序列
#     "tn":当前最新的临时寄存器编号
#     "res":当前结果存放在哪个变量中
#   }
'''


'''
【说明】基于LittleC规则的算术表达式分析器 接收tokens(token序列)作为输入 最终输出语法错误 或 (正确时)有意义的结果字典 记为retDict
【表达式递归定义】
<Expr> → <Term> <Expr1>
<Expr1> → <AddOp> <Term> <Expr1> | empty
<Term> → <Factor> <Term1>
<Term1> → <MulOp> <Factor> <Term1> | empty
<Factor> → id |number | ( <Expr> )
<AddOp> → + | -
<MulOp> → * | /
###旧数据结构###
【tokens】详情见Lex.py
【needTree】
needTree 是通用的语法树字典 所有语法树的定义形式如下:
基本构成
#  {
#     "root":树根(tag_tokens|None),
#     "leafA":节点A(tag_tokens|子树字典|None)
#     "leafB":节点B(tag_tokens|子树字典|None)
#     "leafC":节点C(tag_tokens|子树字典|None)
#               ...
#     "leafZ":节点Z(tag_tokens|子树字典|None)
#   }
该树的根节点下 可支持最多26个子节点(A~Z) 最少1个子节点 
当根或子节点取为None时，该节点作废 None只为兼容部分递归代码 并无意义
【tag_tokens】
tag_tokens 是分类好的tokens序列 我们将明确检测为完整构成某语法单元的一组token进行整理后，为其打上标签tag 形如[tag,[token,token,...,token] ]
tag 递归定义中出现的语法单元名 看作是分类的标签
tokens token序列
'''

'''
函数表
  |-testExpr(tokens)          检测Expr元素返回结果字典
  |-testExpr1(tokens)         检测Expr1元素返回结果字典
  |-testTerm(tokens)          检测Term元素返回结果字典
  |-testTerm1(tokens)         检测Term1元素返回结果字典
  |-testFactor(tokens)        检测Factor元素返回结果字典
  |-testOp(tokens,tid)        检测Op元素返回结果字典
  |-extractBreaket(tokens)    提取()内的token序列并返回结果字典
  |-getTokens(tokens,id,tid)  安全提取tokens[id][tid]的内容 越界返回空而非报错
'''


#testExpr() 检测并提取Expr元素内容
#tokens  词法单位序列
# 返回一个结果字典 
def testExpr(tokens,tn):
  # print("Expr",tokens)
  needTree={"root":None}
  need=[]
  asmCodes=[]
  #1.检测Term
  retDict1=testTerm(tokens,tn)
  if not retDict1["status"]:
    print("Expr Error!")
    return {"status":0,"need":None,"new":None}
  else:
    need.extend(retDict1["need"])
    needTree["leafA"]=retDict1["needTree"]
    tn=retDict1["tn"]
    asmCodes=updateAsmCodes(asmCodes,retDict1["asmCodes"])
    res=retDict1["res"]

  #2.检测Expr1
  retDict2=testExpr1(retDict1["new"],tn,res)
  if not retDict2["status"]:
    print("Expr Error!")
    return {"status":0,"need":None,"new":None}
  else:
    need.extend(retDict2["need"])
    needTree["leafC"]=retDict2["needTree"]
    tn=retDict2["tn"]
    res=retDict2["res"]
    asmCodes=updateAsmCodes(asmCodes,retDict2["asmCodes"])
    if need !=[]:
      needTree["root"]=["Expr",need]
    return {"status":1,"need":need,"new":retDict2["new"],"needTree":needTree,"tn":tn,"res":res,"asmCodes":asmCodes}




#testExpr1() 检测并提取Expr1元素内容
#tokens  词法单位序列
# 返回一个结果字典 
def testExpr1(tokens,tn,leftv):
  # print("Expr1",tokens)
  need=[]
  asmCodes=[]
  needTree={"root":None}
  if getTokens(tokens, 0, 1)=="":
    return {"status":1,"need":need,"new":tokens,"needTree":needTree,"res":leftv,"tn":tn,"asmCodes":[]}
  #1.检测加减op
  retDitc1=testOp(tokens,0)
  if not retDitc1["status"]:
    print("Expr1 Error!")
    return {"status":0,"need":None,"new":None} 
  else:
    need.extend(retDitc1["need"])
    needTree["leafA"]=retDitc1["needTree"]
  opres=retDitc1["res"]
  #2.检测Term
  retDict2=testTerm(retDitc1["new"],tn)
  if not retDict2["status"]:
    print("Expr1 Error!")
    return {"status":0,"need":None,"new":None} 
  else:
    need.extend(retDict2["need"])
    needTree["leafB"]=retDict2["needTree"]
  tn=retDict2["tn"]
  res=None 
  #若两个是数字 直接求结果 然后放到res里
  # print("hello",retDict2['res'][0],"$$  ",leftv[0])
  if retDict2['res'][0]!='t' and leftv[0]!='t':
    if opres=="+":
      res=str(int(leftv)+int(retDict2['res']))
    else:
      res=str(int(leftv)-int(retDict2['res']))
  #若只有dstArg是数字 为其申请一个tx来保存值 
  elif leftv[0]!='t' and retDict2['res'][0]=='t':
    res="t"+str(tn)
    asmCodes=updateAsmCodes(asmCodes,[{"row":1,"op":"mov","arg1":leftv,"arg2":res,"res":res}])
    asmCodes=updateAsmCodes(asmCodes,retDict2["asmCodes"])
    leftv=res  
    asmCodes=updateAsmCodes(asmCodes,[{"row":1,"op":opres,"arg1":retDict2["res"],"arg2":leftv,"res":leftv}])
    tn=tn+1
  else:
    asmCodes=updateAsmCodes(asmCodes,retDict2["asmCodes"])
    asmCodes=updateAsmCodes(asmCodes,[{"row":1,"op":opres,"arg1":retDict2["res"],"arg2":leftv,"res":leftv}])
    res=leftv
  #3.检测expr1
  retDict3=testExpr1(retDict2["new"],tn,res)
  if not retDict3["status"]:
    print("Expr1 Error!")
    return {"status":0,"need":None,"new":None}
  else:
    asmCodes=updateAsmCodes(asmCodes,retDict3["asmCodes"])
    res=retDict3["res"]
    tn=retDict3["tn"]
    need.extend(retDict3["need"])
    needTree["leafC"]=retDict3["needTree"]
    if need !=[]:
      needTree["root"]=["Expr1",need]
    return {"status":1,"need":need,"new":retDict3["new"],"needTree":needTree,"asmCodes":asmCodes,"res":res,"tn":tn}


#testTerm() 检测并提取Term元素内容
#tokens  词法单位序列
# 返回一个结果字典 
def testTerm(tokens,tn):
  # print("Term",tokens)
  need=[]
  needTree={"root":None}
  asmCodes=[]
  res=None 
  #1.检测Factor
  retDict1=testFactor(tokens,tn)
  if not retDict1["status"]:
    print("Term Error!")
    return {"status":0,"need":None,"new":None}
  else:
    needTree["leafA"]=retDict1["needTree"]
    need.extend(retDict1["need"])
  needTree["leafA"]=retDict1["needTree"]
  tn=retDict1["tn"]
  asmCodes.extend(retDict1["asmCodes"])
  res=retDict1["res"]
  #2.检测Term1(leftv是缺少了的左值)
  retDict2=testTerm1(retDict1["new"],tn,res)
  if not retDict2["status"]:
    print("Term Error!")
    return {"status":0,"need":None,"new":None}
  else:
    need.extend(retDict2["need"])
    needTree["leafB"]=retDict2["needTree"]
    tn=retDict2["tn"]
    res=retDict2["res"]
    asmCodes=updateAsmCodes(asmCodes,retDict2["asmCodes"])
    if need !=[]:
      needTree["root"]=["Term",need]
    return {"status":1,"need":need,"new":retDict2["new"],"needTree":needTree,"asmCodes":asmCodes,"res":res,"tn":tn}



#testTerm1() 检测并提取Term1元素内容
#tokens  词法单位序列
# 返回一个结果字典 
def testTerm1(tokens,tn,leftv):
  asmCodes=[]
  # print("Term1",tokens)
  need=[]
  needTree={"root":None}
  if getTokens(tokens,0,1)=="":
    return {"status":1,"need":need,"new":tokens,"needTree":needTree,"asmCodes":[],"tn":tn,"res":leftv}

  #1.检测乘除op
  retDict1=testOp(tokens, 1)
  if not retDict1["status"]:      #乘除若没匹配则检查加减op
    reDict11=testOp(tokens,0)
    if reDict11["status"]:                    #此处若是加减op 则可认为Term1顺利结束
      return {"status":1,"need":need,"new":tokens,"needTree":needTree,"asmCodes":[],"tn":tn,"res":leftv}
    else:
      print("Term1 Error!")
      return {"status":0,"need":None,"new":None}
  else:
    need.extend(retDict1["need"])
    needTree["leafA"]=retDict1["needTree"]
    opres=retDict1["res"]

  #2.检测Factor
  retDict2=testFactor(retDict1["new"],tn)
  if not retDict2["status"]:
    print("Term1 Error!")
    return {"status":0,"need":None,"new":None}
  else:
    need.extend(retDict2["need"])
    needTree["leafB"]=retDict2["needTree"]
  tn=retDict2["tn"]
  res=None 
  #若两个是数字 直接求结果 然后放到res里
  if retDict2['res'][0]!='t' and leftv[0]!='t':
    if opres=="*":
      res=str(int(leftv)*int(retDict2['res']))
    else:
      res=str(int(leftv)//int(retDict2['res']))
  #若只有dstArg是数字 为其申请一个tx来保存值 
  elif leftv[0]!='t' and retDict2['res'][0]=='t':
    res="t"+str(tn)
    asmCodes=updateAsmCodes(asmCodes,[{"row":1,"op":"mov","arg1":leftv,"arg2":res,"res":res}])
    asmCodes=updateAsmCodes(asmCodes,retDict2["asmCodes"])
    leftv=res  
    asmCodes=updateAsmCodes(asmCodes,[{"row":1,"op":opres,"arg1":retDict2["res"],"arg2":leftv,"res":leftv}])
    tn=tn+1
  else:
    asmCodes=updateAsmCodes(asmCodes,retDict2["asmCodes"])
    asmCodes=updateAsmCodes(asmCodes,[{"row":1,"op":opres,"arg1":retDict2["res"],"arg2":leftv,"res":leftv}])
    res=leftv
  #3.检测Term1
  retDict3=testTerm1(retDict2["new"],tn,res)
  if not retDict3["status"]:
    print("Term1 Error!")
    return {"status":0,"need":None,"new":None}
  else:
    asmCodes=updateAsmCodes(asmCodes,retDict3["asmCodes"])
    res=retDict3["res"]
    tn=retDict3["tn"]
    need.extend(retDict3["need"])
    needTree["leafC"]=retDict3["needTree"]
    if need !=[]:
      needTree["root"]=["Term1",need]
    return {"status":1,"need":need,"new":retDict3["new"],"needTree":needTree,"tn":tn,"res":res,"asmCodes":asmCodes}


#testFactor() 检测并提取Factor元素内容
#tokens  词法单位序列
# 返回一个结果字典 
def testFactor(tokens,tn):
  # print("Factor",tokens)
  #1.检测是否为标识符
  # print(getTokens(tokens,0,0))
  if getTokens(tokens,0,0)==3:
    asmCodes=[{"row":1,"op":"mov","arg1":getTokens(tokens,0,1),"arg2":"t"+str(tn),"res":"t"+str(tn)}]
    return {"status":1,"need":[tokens[0]],"new":tokens[1:],"needTree":["Factor_id",[tokens[0]]],"asmCodes":asmCodes,"tn":tn+1,"res":"t"+str(tn)}  #标识符
  #2.检测是否为数字
  elif getTokens(tokens,0,0)==2:
    need=[tokens[0]] #到了这里
    return {"status":1,"need":need,"new":tokens[1:],"needTree":["Factor_Num",need],"asmCodes":[],"tn":tn,"res":getTokens(tokens,0,1)}  #数字
  #3.检测是否为带括号的表达式
  else:  
    retDict1=extractBreaket(tokens)
    if not retDict1["status"]:
      print("Factor Error!")
      return {"status":0,"need":None,"new":None}
    retDict2=testExpr(retDict1["need"],tn)
    if not retDict2["status"]:
      print("Factor Error!")
      return {"status":0,"need":None,"new":None}
    else:
      need=[[1,"("]]
      need.extend(retDict1["need"])
      need.append([1,")"])
      needTree={"root":["Factor_(expr)",need],"leafA":['Breaket',[[1,"("]]],"leafB":retDict2["needTree"],"leafC":['Breaket',[[1,")"]]]}
      tn=retDict2["tn"]
      res=retDict2["res"]
      asmCodes=retDict2["asmCodes"]
      return {"status":1,"need":need,"new":retDict1["new"],"needTree":needTree,"tn":tn,"res":res,"asmCodes":asmCodes}


#extractBreaket() 提取一层括号中的内容
#expr 表达式字符串
# 返回一个结果字典
#  {
#     "status":结果状态(0找到|1没找到),
#     "need":返回括号内的元素(元素字符串|None),
#     "new":返回)后的tokens(表达式字符串|None),
#   }
def extractBreaket(tokens):
  # print("Breat",tokens)
  count=0
  #1.检测首个是否为(
  if getTokens(tokens,0,1) != '(':
    print("Breaket1 Error!")
    return {"status":0,"need":None,"new":None}
  for index,token in enumerate(tokens):
    if token[1] =="(":
      count+=1
    elif token[1] ==")":
      count-=1
      if count==0:
        return {"status":1,"need":tokens[1:index],"new":tokens[index+1:]}
  print("Breaket2 Error!")
  return {"status":0,"need":None,"new":None}





#testOp() 检测并提取Op元素内容
#tokens  词法单位序列
#tid 检测类型 (0检测加减|1检测乘除)
# 返回一个结果字典 
def testOp(tokens,tid):
  # print("OP",tokens)
  testList=[['+','-'],['*','/']]
  testLabel=["Add","Mul"]
  #检测运算符
  if getTokens(tokens,0,1) in testList[tid]:
    typetext=testLabel[tid]+"Op"
    return {"status":1,"need":[tokens[0]],"new":tokens[1:],"needTree":[typetext,[tokens[0]]],"res":getTokens(tokens,0,1) }
  else:
    # print("Op Error!")
    return {"status":0,"need":None,"new":None}




#getTokens()安全获取token内容
#当token不足时会返还""或-1
#id为token下标
#tid 获取token中的数据下标(0类型说明|1内容)
def getTokens(tokens,id,tid):
  if len(tokens):
    return tokens[id][tid]
  else:
    return "" if tid==1 else -1 

#将newCodes更新行号后,
def updateAsmCodes(oldCodes,newCodes):
  if len(oldCodes)==0:
    return newCodes
  old_startIndex=oldCodes[-1]["row"]
  for line in newCodes:
    if line["op"][0]=="j" and len(line["op"])>1:    #跳转语句要更新行号
      line["arg1"]=line["arg1"]+old_startIndex
    line["row"]=line["row"]+old_startIndex
    oldCodes.append(line)
  return oldCodes





